Journals
  Publication Years
  Keywords
Search within results Open Search
Please wait a minute...
For Selected: Toggle Thumbnails
Optimal task scheduling method based on satisfiability modulo theory for multiple processors with communication delay
JIANG Songyan, LIAO Xiaojuan, CHEN Guangzhu
Journal of Computer Applications    2023, 43 (1): 185-191.   DOI: 10.11772/j.issn.1001-9081.2021111862
Abstract209)   HTML6)    PDF (1508KB)(68)       Save
It is of great significance in the scheduling theory and practice of parallel computing to achieve the minimum execution time of task graphs with communication delays on homogeneous multiple processors. For the task graph scheduling problem with communication delay, an optimization method based on Satisfiability Modulo Theory (SMT) was proposed. Firstly, constraints such as processor mapping constraints and task execution order were encoded, thus the task graph scheduling problem was transformed into an SMT problem. Then, the SMT solver was called to search the feasible solution space to determine the optimal solution of the problem. In the constraint encoding phase, integer variables were introduced to represent the mapping relationships between tasks and processors, thereby reducing the complexity of processor constraint encoding. In the solver calling phase, the constraints of independent tasks were added to reduce the search space of the solver and further improve the search efficiency of the optimal solution. Experimental results show that compared with the original SMT method, the improved SMT method reduces the average solving time by 65.9% and 53.8% in timeout experiments of 20 seconds and 1 minute, respectively, and achieves a greater efficiency advantage when the number of processors is relatively large. The improved SMT method can effectively solve the task graph scheduling problem with communication delay, especially be suitable for scheduling scenarios with a large number of processors.
Reference | Related Articles | Metrics